import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode894 {

    // 使用HashMap进行记忆化存储
    Map<Integer, List<TreeNode>> memo = new HashMap<>();

    public List<TreeNode> allPossibleFBT(int n) {
        // 如果已经计算过，直接返回结果
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        List<TreeNode> result = new ArrayList<>();

        // 基本情况：只有一个节点的树
        if (n == 1) {
            result.add(new TreeNode(0));
            memo.put(1, result);
            return result;
        }

        // n必须是奇数才能构成满二叉树
        if (n % 2 == 0) {
            return result; // 返回空列表
        }

        // 构造所有的满二叉树
        for (int i = 1; i < n; i += 2) {
            int leftNodes = i;
            int rightNodes = n - 1 - leftNodes;

            List<TreeNode> leftTrees = allPossibleFBT(leftNodes);
            List<TreeNode> rightTrees = allPossibleFBT(rightNodes);

            // 组合左右子树
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }

        // 记忆化存储结果
        memo.put(n, result);
        return result;
    }
}
